<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 1. 三数之和
        // 时间复杂度：O(nlogn)是排序的，内层循环是O(n^2)，总的时间复杂度是O(n^2)
        // 空间复杂度：O(1)
        var threeSum = function(nums) {
            // 先排序
            nums.sort((a, b) => a - b)
            const ans = []
            const n = nums.length
            // 必须写i小于n-3
            for (let i = 0; i < n - 2; i++) {
                const x = nums[i]
                // 跳过重复数字
                if (i > 0 && x === nums[i - 1]) continue
                
                // 三个最小值都比target大，直接break
                if (x + nums[j] + nums[k] > target) break
                // 如果当前值和最后两个数加起来比target小，则continue
                if (x + nums[n - 1] + nums[n - 2] < target) continue

                let j = i + 1 // j指针，比i大一个
                let k = n - 1 // k指针，从结尾开始往前
                while (j < k) {
                    let sum = nums[i] + nums[j] + nums[k]
                    // 求和值小了，让j指针向前移动
                    if (sum < 0) {
                        j++
                    } else if (sum > 0) {
                        // 求和值大了，让k指针后移动
                        k--
                    } else {
                        // 找到等于0的值
                        ans.push([nums[i], nums[j], nums[k]])
                        // 如果当前枚举和上一次枚举的数字一样，要跳过
                        for (j++; j < k && nums[j] === nums[j - 1]; j++) continue
                        for (k--; j < k && nums[k] === nums[k + 1]; k--) continue
                    }
                }
            }
            return ans
        };
        console.log(threeSum([0, 0, 0]));
        // console.log(threeSum([-1, 0, 1, 2, -1, -4]));
        // [-1,0,1,2,-1,-4]
        // console.log(threeSum([-5, 1, 3, 7, 4, 2]));
        // console.log(threeSum([1]));
    </script>
</body>
</html>